﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution105
{
    Dictionary<int, int> map;
    public TreeNode BuildTree(int[] preorder, int[] inorder)
    {
        map=new Dictionary<int, int>();

        for (int i = 0; i < inorder.Length ; i++)
        {
            map.Add(inorder[i], i);

        }

        return DFS(preorder, inorder,0, preorder.Length-1, 0, preorder.Length - 1);
     
    }

    private TreeNode DFS(int[] preorder, int[] inorder,int preorderstart, int preorderend, int inorderstart, int inorderend)
    {


        if(preorderstart > preorderend)
        {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preorderstart]);



        //使用hash代替
        //for (int i = inorderstart; i < inorderend; i++)
        //{
        //    if (inorder[i] == preorder[preorderstart])
        //    {
        //        mid = i;
        //    }

        //}
        //inorder的根节点

        int mid = map[preorder[preorderstart]];



        int leftLen = mid - inorderstart;
        
        ////左孩子递归

        //root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + leftLen, inorder_left, inorder_root - 1);


        ////右孩子递归
        //root.right = myBuildTree(preorder, inorder, preorder_left + leftLen + 1, preorder_right, inorder_root + 1, inorder_right);


        root.left = DFS(preorder, inorder, preorderstart+1, preorderstart+ leftLen, inorderstart,mid-1);
        root.right = DFS(preorder, inorder, preorderstart + leftLen+1, preorderend, mid + 1, inorderend);
        return root;

    }

    Dictionary<int, int> map2 = new Dictionary<int, int>();//key是inorder的值，value是inorder的index
    public TreeNode BuildTree1(int[] preorder, int[] inorder)//递归法
    {

        int len = preorder.Length;
        for (int i = 0; i < inorder.Length; i++)//方便找根的位置
        {

            map2[inorder[i]] = i;


        }



        return myBuildTree(preorder, inorder, 0, len - 1, 0, len - 1);


    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right)

    {


        if (preorder_left > preorder_right)
        {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preorder_left]);//当前的根节点是先序遍历的第一个
                                                              //左孩子是中序遍历左边的，右孩子是右边的


        int inorder_root = map2[preorder[preorder_left]];//1
        int leftLen = inorder_root - inorder_left;//1-0=1
                                                  //int rigntLen = inorder_right- inorder_root ;//4-1=3,用不到




        //左孩子递归

        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + leftLen, inorder_left, inorder_root - 1);


        //右孩子递归
        root.right = myBuildTree(preorder, inorder, preorder_left + leftLen + 1, preorder_right, inorder_root + 1, inorder_right);

        return root;
    }
}
class Program105
{
    static void Main105(string[] args)
    {

        int[] preorder = [3, 9, 20, 15, 7];
        int[] inorder = [9, 3, 15, 20, 7];
        Solution105 solution = new Solution105();
        TreeNode root = solution.BuildTree(preorder, inorder);
        Solution102 LevelOrder = new Solution102();
        IList<IList<int>> res = LevelOrder.LevelOrder(root);
        for (int i = 0; i < res.Count; i++)
        {
            for (int j = 0; j < res[i].Count; j++)
            {


                Console.Write(res[i][j] + ",");
            }
            Console.WriteLine();
        }
    }
}
